package top.ivansong92.example.leetcode.learning.data.struct.tree;


import java.util.*;

public class TestExampleV2 {
    /**
     * Definition for a binary tree node.
     */
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }


    /**
     * 112. 路径总和
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        if (root.right == null && root.left == null) {
            return root.val == targetSum;
        }

        return doMatchPath(root.left, targetSum, root.val) || doMatchPath(root.right, targetSum, root.val);
    }

    private boolean doMatchPath(TreeNode node, int target, int parent) {
        if (node == null) {
            return false;
        }

        int val = node.val + parent;
        if (node.left == null && node.right == null) {
            return val == target;
        }

        return doMatchPath(node.left, target, val) || doMatchPath(node.right, target, val);
    }


    /**
     * 404. 左叶子之和
     * {1、节点的值均为非负数？ 2、如果存在负数且没有左子树的情况下该如何返回值}
     * @param root
     * @return
     */
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }

        List<Integer> list = new ArrayList<>();

        doSumLeft(root.left, true, list);

        doSumLeft(root.right, false, list);

        return list.stream().mapToInt(Integer::intValue).sum();
    }

    private void doSumLeft(TreeNode node, boolean left, List<Integer> list) {
        if (node == null) {
            return;
        }

        if (left && node.right == null && node.left == null) {
            list.add(node.val);
        }

        doSumLeft(node.left, true, list);

        doSumLeft(node.right, false, list);
    }

    public int sumOfLeftLeavesV2(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return doSumLeftLe(root.left, true) + doSumLeftLe(root.right, false);
    }

    private int doSumLeftLe(TreeNode node, boolean left) {
        if (node == null) {
            return 0;
        }

        if (left && node.right == null && node.left == null) {
            return node.val;
        }

        return doSumLeftLe(node.left, true) +  doSumLeftLe(node.right, false);
    }

    /**
     * 257. 二叉树的所有路径
     * @param root
     * @return
     */
    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }

        if (root.left == null && root.right == null) {
            return Collections.singletonList(root.val + "");
        }

        List<String> res = new ArrayList<>();

        doSearchTree(root.left, res, root.val + "");

        doSearchTree(root.right, res, root.val + "");

        return res;
    }

    private void doSearchTree(TreeNode node, List<String> list, String parent) {
        if (node == null) {
            return;
        }

        String path = parent + "->" + node.val;
        if (node.left == null && node.right == null) {
            list.add(path);
            return;
        }

        if (node.left != null) {
            doSearchTree(node.left, list, path);
        }

        if (node.right != null) {
            doSearchTree(node.right, list, path);
        }

    }


    /**
     * 113. 路径总和 II
     * @param root
     * @param targetSum
     * @return
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return Collections.emptyList();
        }

        if (root.right == null && root.left == null) {
            return root.val == targetSum ? Collections.singletonList(Collections.singletonList(root.val)) : Collections.emptyList();
        }


        List<List<Integer>> res = new ArrayList<>();
        List<Integer> parent = Arrays.asList(root.val);
        if (root.left != null) {
            doSearchMatchPath(root.left, parent, res, targetSum, root.val);
        }

        if (root.right != null) {
            doSearchMatchPath(root.right, parent, res, targetSum, root.val);
        }
        return res;
    }

    private void doSearchMatchPath(TreeNode node, List<Integer> parent, List<List<Integer>> list,  int targetSum, int parentVal) {
        int val = node.val + parentVal;

        List<Integer> pathList = new ArrayList<>(parent);
        pathList.add(node.val);
        if (node.left == null && node.right == null) {
            if (val == targetSum) {
                list.add(pathList);
            }
            return;
        }

        if (node.left != null) {
            doSearchMatchPath(node.left, pathList, list, targetSum, val);
        }

        if (node.right != null) {
            doSearchMatchPath(node.right, pathList, list, targetSum, val);
        }
    }


    /**
     * 129. 求根节点到叶节点数字之和
     * @param root
     * @return
     */
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.right == null && root.left == null) {
            return root.val;
        }
        return doSumNum(root.left, root.val) + doSumNum(root.right, root.val);
    }

    private int doSumNum(TreeNode node, int parent) {
        if (node == null) {
            return 0;
        }

        int val = parent * 10 + node.val;
        if (node.left == null && node.right == null) {
            return val;
        }

        return doSumNum(node.left, val) + doSumNum(node.right, val);
    }


    public int sumNumbersV2(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.right == null && root.left == null) {
            return root.val;
        }

        List<String> pathList = new ArrayList<>();

        doSumNumV2(root.left, root.val + "", pathList);
        doSumNumV2(root.right, root.val + "", pathList);

        return pathList.parallelStream().mapToInt(Integer::valueOf).sum();
    }

    private void doSumNumV2(TreeNode node, String parent, List<String> pathList) {
        if (node == null) {
            return;
        }

        String val = parent + node.val;
        if (node.left == null && node.right == null) {
            pathList.add(val);
            return;
        }

        doSumNumV2(node.left, val, pathList);
        doSumNumV2(node.right, val, pathList);
    }



    public static TreeNode stringToTreeNode(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return null;
        }

        String[] parts = input.split(",");
        String item = parts[0];
        TreeNode root = new TreeNode(Integer.parseInt(item));
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);

        int index = 1;
        while(!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int leftNumber = Integer.parseInt(item);
                node.left = new TreeNode(leftNumber);
                nodeQueue.add(node.left);
            }

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int rightNumber = Integer.parseInt(item);
                node.right = new TreeNode(rightNumber);
                nodeQueue.add(node.right);
            }
        }
        return root;
    }


    public static String booleanToString(boolean input) {
        return input ? "True" : "False";
    }
}
